返回

转到题目

这种题目，看起来很像某种算法题，但是实际上就是一个显然性质的思维推导 瓶颈之处就是板子题目做多了，就很难想到这种题目，不容易从圈中跳出来。

何解?

• 深度理解某些算法的核心性质，没有学精的算法不要考虑，因为这种思维会让你陷入思维陷阱

  思路

• 我要求的是最小的 循环节”数”,然后还知道，可以插入任意字符，以找到这个最小的循环节。
• 首先我们要看一下，什么是循环节。
  • 循环节，循环节的构成一般是什么呢？abc这种?abca呢?
    • 他们都是符合循环节的定义.但是你要知道的是你现在的操作”度“是无穷的
    • 而你要找到最小的循环节 abca这种可能吗？
      • 它含有相同字符就意味着，它还是可以分割的，意味着它不是最小的。
      • 所以最小的循环节数意味着他不能含有相同字符。
      • 恰好没有重复元素是符合条件的,那能不能更小呢？
        • 如果一个串已经不重复字符了，就不能让循环节更小了。因为这个题目是只能插入不能删除的，连相同都不相同，更不可能分离成两个循环节，因为一定会导致不成立
        • 所以，最小的不重复字符循环节 就是最长的不重复字符子串。
• 所以，我们可以先求出这个串的最长不重复子串，就是答案
• 而我们再此实际上分析的还不是很准确，由于它不能删除，也就是导致，这个字符串中不同字符的数量就决定着最长不重复子串的长度。

参考代码

#include <bits/stdc++.h>
using namespace std;
string s;
int cnt[100];//这里能容纳26 *2 个位置就可以，我开的100
int res=0;
int main(){
    cin>>s;
    for (auto x:s){
        cnt[x-'A']++;
    }
    for (int i = 0;i<100;i++){
        res += (cnt[i]>0);
    }
    cout<<res;
    return 0;
}

这里有大佬的建议